package leetcode;
/**
 * 206.反转链表
 * 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
 * 输入：head = [1,2,3,4,5]
 * 输出：[5,4,3,2,1]
 */
public class Num_206 {
    //方法一：头插法，不考虑空间复杂度
    public ListNode reverseList(ListNode head) {
        //考虑[]和[1]的情况
        if(head == null || head.next == null){
            return head;
        }
        //创建新的链表，dummyHead作为虚拟头节点
        ListNode dummyHead = new ListNode(-5001);
        //遍历原来的链表，并把它的元素头插法插入新的链表
        while(head != null){
            //头插法
            ListNode node = new ListNode(head.val);
            node.next = dummyHead.next;
            dummyHead.next = node;
            //head右移，继续循环
            head = head.next;
        }
        return dummyHead.next;
    }

    //方法二：原地移动，空间复杂度为O(1)
    public ListNode reverseList2(ListNode head){
        //考虑[]和[1]的情况
        if(head == null || head.next == null){
            return head;
        }
        //待处理节点的前驱
        ListNode prev = null;
        //cur表示当前需要处理的节点
        ListNode cur = head;
        //next暂存下一个节点
        ListNode next = cur.next;
        while(cur != null){
            //next位于cur的下一位
            next = cur.next;
            cur.next = prev;
            //prev右移
            prev = cur;
            //cur右移
            cur = next;
        }
        return prev;
    }

    //方法三：递归，简单
    public ListNode reverseList3(ListNode head){
        //考虑[]和[1]的情况
        if(head == null || head.next == null){
            return head;
        }
        //先暂存head下一个节点的位置
        ListNode sec = head.next;
        //再把head以后的链表反转
        ListNode newHead = reverseList(head.next);
        //此时sec在链表的最后一位，将它指向原本的头节点head
        sec.next = head;
        //最后将原本的head指向空,防止末尾有环
        head.next = null;
        return newHead;
    }

    /************ 测试  ***************/
    //主方法
    public static void main(String[] args) {
        //建立一个链表头
        ListNode head = build();
        //创建对象，并引用对象中的方法
        Num_206 s = new Num_206();
        ListNode newHead = s.reverseList(head);
        System.out.println("输入："+show(head));
        System.out.println("输出："+show(newHead));
    }
    //创建一个链表
    public static ListNode build(){
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        return node1;
    }
    //打印链表
    public static String show(ListNode head){
        String str = "";
        ListNode temp = head;
        while(temp != null){
            str += temp.val;
            str += " -> ";
            temp = temp.next;
        }
        str += "NULL";
        return str;
    }
}
